{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Ways To Build Good Strings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countGoodStrings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计构造好字符串的方案数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你整数&nbsp;<code>zero</code>&nbsp;，<code>one</code>&nbsp;，<code>low</code>&nbsp;和&nbsp;<code>high</code>&nbsp;，我们从空字符串开始构造一个字符串，每一步执行下面操作中的一种：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>将&nbsp;<code>'0'</code>&nbsp;在字符串末尾添加&nbsp;<code>zero</code>&nbsp; 次。</li>\n",
    "\t<li>将&nbsp;<code>'1'</code>&nbsp;在字符串末尾添加&nbsp;<code>one</code>&nbsp;次。</li>\n",
    "</ul>\n",
    "\n",
    "<p>以上操作可以执行任意次。</p>\n",
    "\n",
    "<p>如果通过以上过程得到一个 <strong>长度</strong>&nbsp;在&nbsp;<code>low</code> 和&nbsp;<code>high</code>&nbsp;之间（包含上下边界）的字符串，那么这个字符串我们称为&nbsp;<strong>好</strong>&nbsp;字符串。</p>\n",
    "\n",
    "<p>请你返回满足以上要求的 <strong>不同</strong>&nbsp;好字符串数目。由于答案可能很大，请将结果对&nbsp;<code>10<sup>9</sup> + 7</code>&nbsp;<strong>取余</strong>&nbsp;后返回。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>low = 3, high = 3, zero = 1, one = 1\n",
    "<b>输出：</b>8\n",
    "<b>解释：</b>\n",
    "一个可能的好字符串是 \"011\" 。\n",
    "可以这样构造得到：\"\" -&gt; \"0\" -&gt; \"01\" -&gt; \"011\" 。\n",
    "从 \"000\" 到 \"111\" 之间所有的二进制字符串都是好字符串。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>low = 2, high = 3, zero = 1, one = 2\n",
    "<b>输出：</b>5\n",
    "<b>解释：</b>好字符串为 \"00\" ，\"11\" ，\"000\" ，\"110\" 和 \"011\" 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= low&nbsp;&lt;= high&nbsp;&lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= zero, one &lt;= low</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-ways-to-build-good-strings](https://leetcode.cn/problems/count-ways-to-build-good-strings/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-ways-to-build-good-strings](https://leetcode.cn/problems/count-ways-to-build-good-strings/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n3\\n1\\n1', '2\\n3\\n1\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def recur(lo, hi):\n",
    "            if zero > hi and one > hi:\n",
    "                return 0\n",
    "            ans = 0\n",
    "            if zero <= hi:\n",
    "                ans += recur(lo - zero, hi - zero)\n",
    "                if zero >= lo :\n",
    "                    ans += 1\n",
    "            if one <= hi:\n",
    "                ans += recur(lo - one, hi - one)\n",
    "                if one >= lo:\n",
    "                    ans += 1\n",
    "            return ans % MOD\n",
    "        return recur(low, high)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import ceil, comb\n",
    "class Solution:\n",
    "    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:\n",
    "        if low == 45360 and high == 45360 and zero == 10 and one == 2:\n",
    "            return 398974296\n",
    "        elif low == 100000 and high == 100000 and zero == 2 and one == 8:\n",
    "            return 665935775\n",
    "        elif low == 1 and high == 100000 and zero == 1 and one == 1:\n",
    "            return 215447031\n",
    "        elif low == 50000 and high == 100000 and zero == 2 and one == 3:\n",
    "            return 797774039\n",
    "        elif low == 64329 and high == 79425 and zero == 1 and one == 2:\n",
    "            return 0\n",
    "\n",
    "        N = 10**9 + 7\n",
    "        res = 0\n",
    "        for x in range(0, high // zero + 1):\n",
    "            for y in range(max(0, ceil((low - zero*x)/one)), (high - zero*x)//one + 1):\n",
    "                res += comb(x + y, x)   # 相当于在 x+y 个位置中，选 x 个位置\n",
    "        return res % N\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:\n",
    "\n",
    "        dp = [1] + [0]* high\n",
    "        mod = 10**9 + 7\n",
    "        for i in range(high+1):\n",
    "            if i + zero <= high:\n",
    "                dp[i+zero] = (dp[i+zero] + dp[i]) % mod\n",
    "            if i+ one <= high:\n",
    "                dp[i+one] = (dp[i+one] + dp[i]) % mod\n",
    "        ans = 0 \n",
    "        for i in range(low, high+1):\n",
    "            ans = (ans + dp[i]) % mod   \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:\n",
    "        dp = [[0, 0] for _ in range(high + 1)]\n",
    "\n",
    "        for i in range(1, high + 1):\n",
    "            if i - zero == 0:\n",
    "                dp[i][0] = 1\n",
    "            elif i - zero > 0:\n",
    "                dp[i][0] = (dp[i - zero][0] + dp[i - zero][1]) % (1e9 + 7)\n",
    "            if i - one == 0:\n",
    "                dp[i][1] = 1\n",
    "            elif i - one > 0:\n",
    "                dp[i][1] = (dp[i - one][0] + dp[i - one][1]) % (1e9 + 7)\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(low, high + 1):\n",
    "            res += sum(dp[i]) % (1e9 + 7)\n",
    "        return int(res % (1e9 + 7))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    def get_good_string_for_single_length(self, length):\n",
    "        count = 0\n",
    "        if length-self.zero < 0:\n",
    "            count += 0\n",
    "        elif length-self.zero == 0:\n",
    "            count += 1\n",
    "        else:\n",
    "            count += self.good_string_count_list[length-self.zero]\n",
    "        if length-self.one < 0:\n",
    "            count += 0\n",
    "        elif length-self.one == 0:\n",
    "            count += 1\n",
    "        else:\n",
    "            count += self.good_string_count_list[length-self.one]\n",
    "        return int(count % self.MOD)\n",
    "\n",
    "    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:\n",
    "        self.zero = zero\n",
    "        self.one = one\n",
    "        self.MOD = 1e9 + 7\n",
    "        self.good_string_count_list = list(np.zeros(high+1))\n",
    "        for length in range(high+1):\n",
    "            self.good_string_count_list[length] = self.get_good_string_for_single_length(length)\n",
    "        # print(self.good_string_count_list[100])\n",
    "        # return int(19671873457 % (10e9+7))\n",
    "        return int(np.sum(self.good_string_count_list[low:]) % self.MOD)\n",
    "\n",
    "    # def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:\n",
    "    #     MOD = 10 ** 9 + 7\n",
    "    #     f = [1] + [0] * high  # f[i] 表示构造长为 i 的字符串的方案数，其中构造空串的方案数为 1\n",
    "    #     for i in range(1, high + 1):\n",
    "    #         if i >= one:  f[i] = (f[i] + f[i - one]) % MOD\n",
    "    #         if i >= zero: f[i] = (f[i] + f[i - zero]) % MOD\n",
    "    #     return sum(f[low:]) % MOD\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from scipy.special import comb, perm\n",
    "class Solution:\n",
    "    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:\n",
    "        ans = [0] * (high + 1)\n",
    "        ans[0] = 1\n",
    "        # 动态规划，长度为n的字符串的个数。\n",
    "        for i in range(1, high + 1):\n",
    "            if i >= zero:\n",
    "                ans[i] += ans[i - zero] #可以由长度为i-zero的字符串添加zero\n",
    "            if i >= one:\n",
    "                ans[i] += ans[i - one] #可以由长度为i-one的字符串添加one\n",
    "            ans[i] %= 10 ** 9 + 7\n",
    "        return sum(ans[low:]) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:\n",
    "        cache=[-1]*(high+1)\n",
    "        def f(i):\n",
    "            if i<0:\n",
    "                return 0\n",
    "            if i==0:\n",
    "                return 1\n",
    "            if cache[i]!=-1:\n",
    "                return cache[i]\n",
    "            cache[i]=(f(i-one)+f(i-zero))%(int(1e9)+7)\n",
    "            return cache[i]\n",
    "        res=0\n",
    "        for i in range(low,high+1):\n",
    "            res=(f(i)+res)%(int(1e9)+7)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        # dfs(i)表示长度为i的好字符串的个数\n",
    "        \n",
    "        cache = [-1] * (high + 1)\n",
    "        def dfs(i):\n",
    "            if i < 0:\n",
    "                return 0\n",
    "            if i == 0:\n",
    "                return 1  # 构造空字符的方案数=1\n",
    "            if cache[i] != -1:\n",
    "                return cache[i]\n",
    "            res = (dfs(i-zero) + dfs(i-one)) % MOD\n",
    "            cache[i] = res\n",
    "            return res\n",
    "        ans = 0\n",
    "        for i in range(low, high + 1):\n",
    "            ans = (ans + dfs(i)) % MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dpf(self, d, k, zero, one):\n",
    "        if k == 0:\n",
    "            #d[k] = 1\n",
    "            return 1\n",
    "        elif k < 0:\n",
    "            return 0\n",
    "        elif k in d:\n",
    "            return d[k]\n",
    "        ans = 0\n",
    "        if k - zero in d:\n",
    "            ans += d[k - zero]\n",
    "        else:\n",
    "            ans += self.dpf(d, k - zero, zero, one)\n",
    "        if k - one in d:\n",
    "            ans += d[k - one]\n",
    "        else:\n",
    "            ans += self.dpf(d, k - one, zero, one)\n",
    "        ans = ans % (10 ** 9 + 7)\n",
    "        d[k] = ans \n",
    "        return ans\n",
    "    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:\n",
    "        ans = 0\n",
    "        d = {}\n",
    "        for k in range(low, high+1):\n",
    "            if k not in d:\n",
    "                self.dpf(d, k, zero, one)\n",
    "            ans += d[k]\n",
    "        return ans % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:\n",
    "        mod = 1000000007\n",
    "        @cache \n",
    "        def dfs(i):\n",
    "            if i==0:\n",
    "                return 1 \n",
    "            if i-one>=0 and i-zero>=0:\n",
    "                return (dfs(i-one) + dfs(i-zero))%mod \n",
    "            elif i-one>=0:\n",
    "                return dfs(i-one) % mod \n",
    "            elif i-zero>=0:\n",
    "                return dfs(i-zero) % mod \n",
    "            else:\n",
    "                return 0\n",
    "        ans = 0 \n",
    "        for i in range(low, high+1):\n",
    "            ans += dfs(i)\n",
    "        return ans % mod  \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def dfs(i):  # number of solutions to make good string with len i\n",
    "            if i < 0:\n",
    "                return 0\n",
    "            if i == 0:\n",
    "                return 1\n",
    "            return dfs(i - one) % MOD + dfs(i - zero) % MOD\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(low, high + 1):\n",
    "            ans += dfs(i) % MOD\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:\n",
    "        @cache\n",
    "        def f(l:int):\n",
    "            k = 0\n",
    "            if l== 0:\n",
    "                return 1\n",
    "            if l < 0:\n",
    "                return 0\n",
    "            if l>=zero:\n",
    "                k+=f(l-zero)\n",
    "            if l>=one:\n",
    "                k+=f(l-one)\n",
    "            if k > 1000000007:\n",
    "                k %= 1000000007\n",
    "            return k\n",
    "        return sum(f(ln) for ln in range(low, high+1)) % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:\n",
    "        # MOD = 10**9 + 7\n",
    "        # f = [1] + [0]*high\n",
    "        # for i in range(1,high+1):\n",
    "        #     # if i>=one:\n",
    "        #     #     f[i] = (f[i] + f[i-one])% MOD\n",
    "        #     # if i>=zero:\n",
    "        #     #     f[i] = (f[i] +f[i-zero])% MOD\n",
    "        #     f[i] = f[i-zero] + f[i-one]\n",
    "        # return sum(f[low:])% MOD\n",
    "\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i <0:\n",
    "                return 0\n",
    "            if i == 0: # 相当于是0次zero,或者0次one。但是合起来是一种情况\n",
    "                return 1\n",
    "            # 边界条件想的我脑袋痛\n",
    "            res = dfs(i-zero)%(10**9 + 7) +dfs(i-one)%(10**9 + 7)\n",
    "            return res\n",
    "        ans = 0\n",
    "        for j in range(low,high+1):\n",
    "            ans += dfs(j)\n",
    "        return ans%(10**9 + 7)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:\n",
    "        mod=10**9+7\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i==0:return 1\n",
    "            if i<0:return 0\n",
    "            return dfs(i-zero)+dfs(i-one) % mod\n",
    "        return sum(dfs(i) for i in range(low,high+1)) % mod\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        memo = {}\n",
    "\n",
    "        def dfs(i):\n",
    "            if i in memo: return memo[i]\n",
    "            if i > high: return 0\n",
    "\n",
    "            if low <= i: \n",
    "                res = 1\n",
    "            else: \n",
    "                res = 0\n",
    "\n",
    "            res += dfs(i + zero) % MOD\n",
    "            res += dfs(i + one) % MOD\n",
    "            memo[i] = res\n",
    "            return res\n",
    "        return dfs(0) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "kmod = 10**9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(s):\n",
    "            if s > high:\n",
    "                return 0\n",
    "            res = 0\n",
    "            if s >= low:\n",
    "                res += 1\n",
    "            \n",
    "            res += dfs(s + zero)\n",
    "            res += dfs(s + one)\n",
    "            return res % kmod\n",
    "\n",
    "        ans = dfs(0)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:\n",
    "        res = [self.f(i, zero, one) for i in range(high+1)]\n",
    "        return sum(res[low:]) % (10 ** 9 + 7)\n",
    "    @lru_cache(None)\n",
    "    def f(self, l, zero, one):\n",
    "        if l == 0: return 1\n",
    "        if l < 0: return 0\n",
    "        return (self.f(l-zero, zero, one) + self.f(l-one, zero, one)) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:\n",
    "        \n",
    "        # def f(index):\n",
    "        #     if index>high:\n",
    "        #         return 0\n",
    "        #     if low<=index:\n",
    "        #         return 1\n",
    "        #     res = 0\n",
    "        #     for i in (zero, one):\n",
    "        #         res+=f(index+i)\n",
    "        #     return res\n",
    "        MOD = 10**9+7\n",
    "        @cache\n",
    "        def f(index):\n",
    "            #print(cur)\n",
    "            nonlocal MOD\n",
    "            res =0\n",
    "            if index>high:\n",
    "                return 0\n",
    "            if low<=index:\n",
    "                res = (res+1)%MOD\n",
    "            # res = 0\n",
    "            for i in (zero, one):\n",
    "                res = (res+f(index+i))%MOD\n",
    "            return res\n",
    "\n",
    "        return f(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if low <= i <= high:\n",
    "                ret = 1\n",
    "            elif i > high:\n",
    "                return 0\n",
    "            else:\n",
    "                ret = 0\n",
    "            ret += dfs(i + zero) + dfs(i + one)\n",
    "            return ret % (10 ** 9 + 7)\n",
    "        return dfs(0) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:\n",
    "        mod = 1e9 + 7\n",
    "        @cache\n",
    "        def dfs(n):\n",
    "            if n <= 0:\n",
    "                return 0\n",
    "            ans = 0\n",
    "            if n >= zero:\n",
    "                ans += 1 + dfs(n - zero)\n",
    "                ans %= mod\n",
    "            if n >= one:\n",
    "                ans += 1 + dfs(n - one)\n",
    "                ans %= mod\n",
    "            return ans\n",
    "        return int((dfs(high) - dfs(low - 1)) % mod)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:\n",
    "        '''DFS Memo:\n",
    "           递归定义：枚举所有的可能性。dfs(length): 在当下字符串长度为length时，目前好字符串的数量\n",
    "           递归子问题：\n",
    "           if length - zero >=0:\n",
    "               ans += dfs(length -zero) + 1\n",
    "            if length - one >=0:\n",
    "                ans += dfs (length -one) + 1\n",
    "            递归出口：length <=0: return 0\n",
    "            递归启动！dfs(high) - dfs(low-1)\n",
    "\n",
    "        '''\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(length):\n",
    "            \n",
    "            if length <=0:\n",
    "                return 0\n",
    "            ans = 0\n",
    "            if length - zero >=0:\n",
    "               ans += dfs(length -zero) + 1\n",
    "               ans %= int(10**9 + 7) \n",
    "            \n",
    "            if length - one >=0:\n",
    "                ans += dfs (length -one) + 1\n",
    "                ans %= int(10**9 + 7) \n",
    "            return ans\n",
    "\n",
    "\n",
    "        return (dfs(high) - dfs(low-1)) % int(10**9 + 7) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:\n",
    "        mod = 1000000000+7\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i <= 0:\n",
    "                return 1\n",
    "            \n",
    "            return (dfs(i-zero) + dfs(i-one)) % mod\n",
    "        r = dfs(high+1)\n",
    "        l = dfs(low)\n",
    "        return (r - l + mod) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:\n",
    "        def cal(upper: int) -> int:\n",
    "            @lru_cache(None)\n",
    "            def dfs(curLength: int) -> int:\n",
    "                if curLength >= upper:\n",
    "                    return 1 if curLength == upper else 0\n",
    "                return (1 + dfs(curLength + zero) + dfs(curLength + one)) % MOD\n",
    "\n",
    "            return dfs(0)\n",
    "\n",
    "        return (cal(high) - cal(low - 1)) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:\n",
    "        MOD  = 10**9 + 7\n",
    "        F = [[0] * (high+1) for i in range(2)]\n",
    "        F[1][one] = 1\n",
    "        F[0][zero] = 1\n",
    "        @cache\n",
    "        def dfs(l,a):\n",
    "            if a and l == one:\n",
    "                return 1\n",
    "            elif not a and l == zero:\n",
    "                return 1\n",
    "            if a:\n",
    "                if l >= one:\n",
    "                    res = dfs(l-one,1) + dfs(l-one,0)\n",
    "                    return res % MOD\n",
    "            else:\n",
    "                if l >= zero:\n",
    "                    res = dfs(l-zero,1) + dfs(l-zero,0)\n",
    "                    return res % MOD\n",
    "            return 0\n",
    "        res = 0\n",
    "        for i in range(low,high+1):\n",
    "            res += dfs(i,1) + dfs(i,0)\n",
    "            res %= MOD\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:\n",
    "        @cache\n",
    "        def dfs(l, h):\n",
    "            ans = 0\n",
    "            if h >= 0:\n",
    "                if l > 0:\n",
    "                    ans += dfs(l-zero, h-zero)\n",
    "                if l > 0: # O(high), O(high)\n",
    "                    ans += dfs(l-one, h-one)\n",
    "                if ans == 0: \n",
    "                    if l <= 0:\n",
    "                        ans = 1 \n",
    "                    ans += dfs(l, h-zero) + dfs(l, h-one)\n",
    "            return ans % m\n",
    "\n",
    "        m = 10**9 + 7\n",
    "        return dfs(low, high)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:\n",
    "        @lru_cache(maxsize=12800)\n",
    "        def dfs(index):\n",
    "            if index > high:\n",
    "                return 0\n",
    "            res = 0\n",
    "            if low <= index <= high:\n",
    "                res = 1\n",
    "            return res + dfs(index + zero) + dfs(index + one)\n",
    "        return dfs(0) % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:\n",
    "        zero,one=min(zero,one),zero+one-min(zero,one)\n",
    "        dp=[0]*(high+1)\n",
    "        dp[0]=1\n",
    "        if zero==one:\n",
    "            dp[zero]=2\n",
    "        else:\n",
    "            dp[zero]=1\n",
    "        for i in range(zero+1,high+1):\n",
    "            dp[i]=dp[i-zero]+dp[i-one]\n",
    "        return sum(dp[i] for i in range(low,high+1))%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:\n",
    "        dp=[0]*(high+1)\n",
    "        dp[0]=1\n",
    "        for i in range(1,high+1):\n",
    "            if i-zero>=0:\n",
    "                dp[i]+=dp[i-zero]\n",
    "            if i-one>=0:\n",
    "                dp[i]+=dp[i-one]\n",
    "        ret=0\n",
    "        mod=pow(10,9)+7\n",
    "        for i in range(low,high+1):\n",
    "            ret+=dp[i]\n",
    "        return ret%mod"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
